/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025-02-21
 * Time: 22:22
 */
//给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
class ListNode1 {
    int val;
    ListNode1 next;
    ListNode1() {}ListNode1(int val) { this.val = val; }
    ListNode1(int val, ListNode1 next) {
        this.val = val;
        this.next = next;
    }
}
class Solution1 {
    public ListNode1 removeElements(ListNode1 head, int val) {
        ListNode1 headPrev = new ListNode1(0,head);
        ListNode1 cur = headPrev;
        while(cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return headPrev.next;
    }
}
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
class ListNode2 {
    int val;
    ListNode2 next;
    ListNode2() {}
    ListNode2(int val) { this.val = val; }
    ListNode2(int val, ListNode2 next) { this.val = val; this.next = next; }
}
class Solution2 {
    public ListNode2 reverseList(ListNode2 head) {
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode2 cur = head.next;
        ListNode2 A = head;
        while(cur.next != null){
            ListNode2 curNext = cur.next;
            cur.next = head;
            A.next = curNext;
            head = cur;
            cur = curNext;
        }
        cur.next = head;
        A.next = null;
        head = cur;
        return head;
    }
}
//给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
//快慢指针
class ListNode3 {
    int val;
    ListNode3 next;
    ListNode3() {}
    ListNode3(int val) { this.val = val; }
    ListNode3(int val, ListNode3 next) { this.val = val; this.next = next; }
}
class Solution {
    public ListNode3 middleNode(ListNode3 head) {
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode3 fast = head;
        ListNode3 slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello, World!");
    }
}